class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> ans(n, 1);

        int before_sum = 1;
        int after_sum = 1;
        for (int i = 0, j = n - 1; i < n, j >= 0; ++i, --j)
        {
            ans[i] *= before_sum;
            before_sum *= nums[i];
            ans[j] *= after_sum;
            after_sum *= nums[j];
        }
        return ans;
    }
};

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
    {
        int n = gas.size(), m = cost.size();
        if (n != m) return -1;
        for (int i = 0; i < n;)
        {

            int len = 0;
            int sum = 0;
            while (len < n)
            {
                int j = (i + len) % n;
                sum += gas[j] - cost[j];
                if (sum < 0)
                {
                    break;
                }
                len++;
            }
            if (len == n) return i;
            else i = i + len + 1;

        }
        return -1;

    }
};


